﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <stdbool.h>
// 原题连接：https://leetcode.cn/problems/sum-of-square-numbers/
/*
题目描述：
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：
输入：c = 3
输出：false
 

提示：
0 <= c <= 231 - 1
*/

// 开始解题：
// 方法1——双指针
bool judgeSquareSum(int c) {
    long long left = 0;
    long long right = (long long)sqrt(c);
    while (left <= right) {
        long long sum = left * left + right * right;
        if (sum == c) {
            return true;
        }
        else if (sum < c) {
            left++;
        }
        else {
            right--;
        }
    }
    return false;
}
// 时间复杂度：O(sqrt(c))。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。